package com.fang.algorithm.leecode;

import java.util.Deque;
import java.util.LinkedList;

/**
 * @author fanglingxiao
 * @version 1.0
 * @description 最长有效括号
 * 给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号子串的长度。
 * <p>
 * 输入：s = "(()"
 * 输出：2
 * 解释：最长有效括号子串是 "()"
 * <p>
 * 输入：s = ")()())"
 * 输出：4
 * 解释：最长有效括号子串是 "()()"
 * <p>
 * 输入：s = ""
 * 输出：0
 * @date 2022/5/18 11:45 上午
 **/
public class L32_LongestValidParentheses {
    public static void main(String[] args) {
        String s = ")()())";
        int ans = longestValidParentheses(s);
        System.out.println(ans);
    }

    private static int longestValidParentheses(String s) {
        if (null == s || s.length() < 2) {
            return 0;
        }
        int ans = 0;
        Deque<Integer> stack = new LinkedList<>();
        stack.push(-1);
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '(') {
                stack.push(i);
            } else {
                stack.pop();
                if (stack.isEmpty()) {
                    // pop + empty的push就是为了过滤掉开头为）的元素真正匹配到（才会继续处理
                    stack.push(i);
                } else {
                    ans = Math.max(ans, i - stack.peek());
                }
            }
        }
        return ans;
    }
}
